package com.dai.linkedlist;


/**
 * 单链表结构
 * 链表是一种最常见的数据结构，其内部数据呈线性排列，属于线性表结构，
 * 什么是线性表:
 * 表中的数据按顺序依次排列，就像用一条线把数据串联起来一样。
 * 链表就是这种排布方式，特点是添加数据和删除数据速度快，
 * 但是查询数据会比较耗时，这是因为链表在内存中的存储结构造成的。
 * <p>
 * 单向链表与双向（循环）链表的区别：
 * <p>
 * 在存储空间方面：
 * 单链表需要的存储空间比双向链表的要少，因为双向链表不仅保存有指向下一个节点的指针，
 * 还保存有指向上一个节点的指针，需要较大的空间来存储双向链表的指针域。
 * <p>
 * 在处理时间方面：
 * 双向链表的插入与删除操作比单链表的时间要快很多。
 * 在最末尾插入的时候，单链表需要找到需要插入位置的前一个节点，需要遍历整个链表，时间复杂度为O（n），
 * 而双向链表只需要head->tail,就可以得到最后一个节点的位置，然后就可以进行插入操作，时间复杂度为O（1）。
 * <p>
 * 在删除操作方面，单链表需要遍历到需要删除的节点的前一个节点，
 * 双向链表需要遍历到需要删除的节点，时间复杂度同为O(n)。
 */
public class LinkedList {

    private int size;

    public Node head;

    public int getSize() {
        return size;
    }


    public void addNode(Object object) {
        size++;
        Node node = new Node(object);
        if (head == null) {
            head = node;
        } else {
            Node node1 = head;
            while (node1.next != null) {
                node1 = node1.next;
            }
            node1.next = node;
        }
    }

    private void printLinkedList(Node node) {
        System.out.println("");
        while (node != null) {
            System.out.print(" --> " + node.data);
            node = node.next;
        }
    }

    public void printLinkedList() {
        printLinkedList(head);
    }

    public void insert(int index, Object object) {
        Node node = new Node(object);

        Node node1 = head;
        if (index == 0) {
            node.next = node1;
            head = node;
            return;
        }

        Node target = null;
        int count = 0;
        while (count != index) {
            target = node1;
            node1 = node1.next;
            ++count;
        }
        node.next = node1;
        target.next = node;
        printLinkedList();
    }

    /**
     * 遍历实现 链表反转
     */
    public void reverse1() {
        Node node = null, temp;
        while (head != null) {
            temp = head.next;
            head.next = node;
            node = head;
            head = temp;
        }

        printLinkedList(node);
        head = node;
    }

    /**
     * 递归方法 进行链表反转
     *
     * @param node
     */
    public Node reverse2(Node node) {
        if (node.next == null) return node;
        Node newNode = reverse2(node.next);
        Node temp = node.next;
        temp.next = node;
        node.next = null;
        printLinkedList(node);
        return newNode;
    }

    public void reverse2() {

        printLinkedList();

        printLinkedList(reverse2(head));

    }

}
